package java_0220.leetcode;

/**
 * 找到最近公共祖先
 * 给定一个二叉树，找到两个指定节点的最近公共祖先
 */
public class Num236_NearestCommonAncestor {
    //最近公共祖先
    private TreeNode nca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //题目给出的条件可知无需判空
        //找到pq的所有祖先
        findNode(root,p,q);
        return nca;
    }

    /**
     * 以当前root为根节点的二叉树是否能找到p或q
     * findNode方法不是找公共祖先的方法，只是判断当前树是否是p或q的祖先，找到一个就说明至少是一个结点的祖先
     * 只是找是否是p或q的祖先的过程中判断了是否是公共祖先
     * @param root
     * @param p
     * @param q
     */
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        //用整型变量记录是否找到节点
        //先在左子树中找p或q
        //若left==1，说明左树至少找到了一个p或q
        int left=findNode(root.left,p,q)?1:0;
        //再在右子树中找p或q
        //若right==1，说明右树至少找到了一个p或q
        int right=findNode(root.right,p,q)?1:0;
        //最后在根节点下判断根节点是否是p或q
        //mid==1，说明根节点就是p或q
        int mid=(root==p||root==q)?1:0;
        if(left+right+mid==2){
            //相加和为2，根节点就是最近公共祖先
            nca=root;
        }
        //否则，有没有祖先就是看就是看上面有没有大于零的数
        return (left+right+mid)>0;
    }
}
